/*
有1个数组r[1...n]，
其中有2个子数组:

	r[1]<r[2]<...<r[m]
	r[m+1]<r[m+2]<...<r[n]。

要求编一空间复杂度为O（1）的程序，
实现数组r[1...n]整体有序。
注意是空间复杂度为O（1）！
*/
#include "junix.h"

void f(int v[], int p,int q,int r) {
	for (int i=q+1;i<=r;i++) {
		int t = v[i];
		for (int j=i-1;j>=0;j--) {
			if (v[j]>t) {
				v[j+1]=v[j];
				if (j==0)
					v[j]=t;
			} else {
				v[j+1]=t;
				break;
			}
		}
	}
}

int main(){
	int v[]={1,3,4,6,2,5,7,9};
	f(v,0,3,7);
	copy(v,v+8,std::ostream_iterator<int>(std::cout," "));
}
